home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / basic / ubmalm.zip / lehmer.ub < prev    next >
Text File  |  1990-08-22  |  1KB  |  26 lines
  1.  1070   *Lehmer(P,Q,&R)
  2.  1080   ' Method of D. H. Lehmer to solve x^2 = Q (mod P), assuming that
  3.  1090   ' P is an odd prime and Q is a quadratic residue modulo P.  The
  4.  1100   ' result is returned in R.
  5.  1110   ' 8 June 1990
  6.  1120   dim Bit%(400) ' Holds bits of (P+1)\2, handles 120-digit numbers
  7.  1130   local Te,H,W,Vs,Vb,T
  8.  1140   local I,J
  9.  1150   Te=P@8:if or{Te=3,Te=7} then R=modpow(Q,(P+1)\4,P):return endif
  10.  1160   if Te=5 then T=modpow(Q,(P-1)\4,P)
  11.  1170   :if T=1 then R=modpow(Q,(P+3)\8,P):return endif
  12.  1180   :R=modpow(4*Q,(P+3)\8,P)
  13.  1190   :if odd(R) then R=(R+P)\2 else R=R\2 endif
  14.  1200   :return endif
  15.  1210   H=1:repeat inc H:until kro(H*H-4*Q,P)=-1
  16.  1220   W=(P+1)\2:J=-1
  17.  1230   repeat inc J:W=W\2:Bit%(J)=res until W=0
  18.  1240   Vs=H:Vb=(H*Vs-2*Q)@P:T=Q
  19.  1250   for I=J-1 to 0 step -1
  20.  1260   Te=2*T
  21.  1270   if Bit%(I) then Vs=(Vs*Vb-H*T)@P:Vb=(Vb*Vb-Q*Te)@P:T=(T*T*Q)@P
  22.  1280   :else Vb=(Vs*Vb-H*T)@P:Vs=(Vs*Vs-Te)@P:T=(T*T)@P endif
  23.  1300   next I
  24.  1310   if odd(Vs) then R=(Vs+P)\2 else R=Vs\2 endif
  25.  1320   return ' End of subroutine Lehmer.
  26.